A linear sequential circuit (LSC) is a sequential circuit in which each next state bit and each output bit is a linear combination with a modulo-2 addition or XOR logic of current state bits and input bits. Two important classes of LSC are a linear feedback shift register (LFSR) and a linear feed forward shift register (LFFSR). A linear feedback shift register can be employed as an additive scrambler, a multiplicative scrambler, an additive descrambler, and/or a turbo encoder. Similarly, a linear feed forward shift register can be employed as a convolution encoder and/or a multiplicative descrambler in a wide range of communication systems.
The majority of prior art linear sequential circuits can be implemented and/or mapped in association with a hardware setup such as, for example, a shift-register. The shift register typically includes a storage element for representing the state bits and XOR gates for representing the modulo-2 additions. Such prior art sequential circuits generate one bit of output in a single clock cycle, which is not adequate for a high-speed wireless communication system. Additionally, a traditional processor/DSP associated with the wireless communication system is not equipped to deal with the linear sequential circuit and each bit in the linear sequential circuit needs to be shifted, masked and manipulated in order to perform the linear sequential circuit computations. Furthermore, such linear sequential circuit requires a number of cycles to implement a single step transition. A look-up table can be alternatively designed to provide a modest computation speed with respect to the linear sequential circuit. Such an approach, however, provides limited computation speedup (usually 8 or less) due to the exponential cost increase required by the larger lookup table to support higher speedup.
Based on the foregoing, it is believed that a need exists for an improved method and system for parallel computation of a linear sequential circuit based on a state transition matrix in order to improve computational speed, as described in greater detail herein.